package qsc.algorithm.hanoitower;

/**
 * @auther QiuShangcheng
 * @create 2021/4/15
 */
public class HanoiTower {
    public static void main(String[] args) {
//        hanoiTower(3,'A','B','C');
        reStudy(3, 'A', 'B', 'C');
    }

    /**
     * 汉诺塔游戏设计（分治算法）
     *
     * 如果 A 塔上有三个盘子：
     * n >= 2 时，就体现出了分治算法的思想：我们将 A 塔上面的盘子看作一个整体，最下面的单个盘子单独分离出来，分三步走
     * 先将 A 塔上面的盘子看作一个整体，移动到 B 塔（把 C 塔当做中转站）
     * 这样 A 塔就只剩下一个最大的盘子，将 A 塔剩下的盘子移动到 C 塔
     * 最后将 B 塔上面的盘子移动到 C 塔（把 A 塔当做中转站）
     *
     *
     *
     * @param num 圆盘数量
     * @param a   a柱子
     * @param b   b柱子
     * @param c   c柱子
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        if (num == 1) {
            System.out.println("第1个盘移动：" + a + "->" + c);
        } else {
            //把A最上面的所有盘移到B去
            hanoiTower(num - 1, a, c, b);
            //把A最下面的盘移到C去
            System.out.printf("第%d个盘移动：%c->%c\n", num, a, c);
            //把B处的所有盘盘移到C去
            hanoiTower(num - 1, b, a, c);
        }
    }


    public static void reStudy(int num, char a, char b, char c) {
        if (num == 1) {
            System.out.println("第1个盘从"+a+"移到"+c+"去");
        } else {
            reStudy(num - 1, a, c, b);
            System.out.printf("第%d个盘从%c移到%c去\n", num, a, c);
            reStudy(num - 1, b, a, c);
        }
    }
}
